package com.test.daily.leetcode.y2022.m07.day0701.v02;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Tom on 2022/7/1
 */
public class Solution {
    public static int ADD_OP = -1;
    public static int ABS_OP = -2;
    public static int MUL_OP = -3;


    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> ops = new ArrayList<>();

        for (int i = 0; i < expression.length(); ) {
            if (!Character.isDigit(expression.charAt(i))) {
                if (expression.charAt(i) == '+') {
                    ops.add(ADD_OP);
                } else if (expression.charAt(i) == '-') {
                    ops.add(ABS_OP);
                } else {
                    ops.add(MUL_OP);
                }
                i++;
            } else {
                int num = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    num = num * 10 + expression.charAt(i) - '0';
                    i++;
                }
                ops.add(num);
            }
        }
        List<Integer> dp[][] = new List[ops.size()][ops.size()];
        for (int L = 0; L < ops.size(); L++) {
            for (int R = 0; R < ops.size(); R++) {

                dp[L][R] = new ArrayList<Integer>();
            }
        }
        return process(dp, ops, 0, ops.size() - 1);
    }

    public List<Integer> process(List<Integer> dp[][], List<Integer> ops, int L, int R) {
        if (dp[L][R].isEmpty()) {
            if (L == R) {
                dp[L][R].add(ops.get(L));
            } else {
                for(int i = L; i < R; i += 2){
                    List<Integer> left = process(dp, ops,L, i);
                    List<Integer> right = process(dp, ops, i + 2, R);
                    int ans = 0;
                    for(int lv: left){
                        for(int rv: right){
                            if(ops.get(i+1) == ADD_OP){
                                ans = lv + rv;
                            } else if(ops.get(i+1) == ABS_OP){
                                ans = lv - rv;
                            } else {
                                ans = lv * rv;
                            }
                            dp[L][R].add(ans);
                        }
                    }
                }
            }
        }
        return dp[L][R];
    }

}
